P4074 [WC2013]糖果公园

发表于

闲扯

这道题可谓是莫队的集大成者。。。

各种各样的方法都用到了。。。

题面

P4074 [WC2013]糖果公园

Solution

将题意简化：

  • 每次询问树上一条路径的权值 $S=\sum_{i=1}^{m}\sum_{j=1}^{num_i}w_j\cdot val_i$ ，其中有修改操作。

如果这道题放在序列上，显然可以直接莫队做，但是这道题上放树上的然后就变成了黑题。

这里引进一种新的技巧：树上莫队。

它用到了一个很奇妙的东西：欧拉序。

欧拉序有这样一个性质：

  • 若 $lca_{u,v}=u$ ，那么在欧拉序上，从 $st_u\rightarrow st_v$ ，只有 $u\rightarrow v$ 这条链上的点恰出现了一次，其他的点出现次数都为 $0$ 或 $2$ 。
  • 若 $lca_{u,v}\not=u,v$ ，我们假设 $dfn_u<dfn_v$ ，那么从 $ed_u\rightarrow st_v$ ，也满足上面的性质，但是需要注意 $lca$ ，它是没有加进去的，所以我们特殊处理一下。

然后我们就将树上的询问转到序列上了。

优化常数的一些小技巧：

  • 分块的大小： $B=n^{\frac{2}{3}}$ （带修莫队的标准大小）。
  • 奇偶排序：如果分别按照左端点，右端点的奇偶性，把右端点，时间轴按照从大到小和从小到大排序。（经过一系列玄学分析，发现它的复杂度很优秀？？？）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int MAXN = 1e5+5;
int n,m,q,val[MAXN],w[MAXN],ty[MAXN],u,v,opt,x,y;
char vis[MAXN];
vector<int> G[MAXN];
il add_edge(int u,int v){
	G[u].push_back(v);
	G[v].push_back(u);
}

// Ê÷ÆÊ LCA 
/*............................*/
int dep[MAXN],son[MAXN],f[MAXN],sz[MAXN],top[MAXN];
il DFS1(int u,int fa){
	dep[u]=dep[fa]+1,sz[u]=1,f[u]=fa;
	for(auto v:G[u]){
		if(v==fa) continue;
		DFS1(v,u),sz[u]+=sz[v];
		if(sz[v]>sz[son[u]]) son[u]=v;
	}
}
il DFS2(int u,int t){
	top[u]=t;
	if(son[u]) DFS2(son[u],t);
	for(auto v:G[u]){
		if(v==f[u]||v==son[u]) continue;
		DFS2(v,v);
	}
}
it LCA(int u,int v){
	while(top[u]^top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		u=f[top[u]];
	}
	return dep[u]<dep[v]?u:v;
}
/*............................*/

// ·Ö¿é 
/*............................*/
int bl[MAXN<<1],dfn[MAXN<<1],st[MAXN],ed[MAXN],cnt,B,t1,t2;
il DFS(int u,int fa){
	dfn[++cnt]=u,st[u]=cnt;
	for(auto v:G[u]){
		if(v==fa) continue;
		DFS(v,u);
	}
	dfn[++cnt]=u,ed[u]=cnt;
}
/*............................*/

// Ī¶Ó 
/*............................*/
struct Node{
	int x,y,lca,tim,id;
	bool operator < (const Node &t) const{
		if(bl[x]^bl[t.x]) return bl[x]<bl[t.x];
		if(bl[y]^bl[t.y]) return bl[x]&1?bl[y]<bl[t.y]:bl[y]>bl[t.y];
		return (bl[x]^bl[y])&1?tim<t.tim:tim>t.tim;
	}
}node[MAXN];
struct Node1{
	int x,y;
}c[MAXN];
int num[MAXN],now;
ll ans[MAXN],res;
il Add(int x){
	if(vis[x]) res-=1ll*w[num[ty[x]]--]*val[ty[x]];
	else res+=1ll*w[++num[ty[x]]]*val[ty[x]];
	vis[x]^=1;
}
il Change(int l,int r,int x){
	if(vis[c[x].x]){
		res+=1ll*w[++num[c[x].y]]*val[c[x].y];
		res-=1ll*w[num[ty[c[x].x]]--]*val[ty[c[x].x]];
	}
	swap(ty[c[x].x],c[x].y);
}
/*............................*/
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m),read(q),B=pow(n*2,2./3);
	for(ri i=1;i<=m;++i) read(val[i]);
	for(ri i=1;i<=n;++i) read(w[i]);
	for(ri i=1;i<n;++i)
		read(u),read(v),add_edge(u,v);
	for(ri i=1;i<=n;++i) read(ty[i]);
	DFS1(1,0),DFS2(1,1),DFS(1,0);
	for(ri i=1;i<=n*2;++i)
		bl[i]=i/B;
	for(ri i=1;i<=q;++i){
		read(opt),read(x),read(y);
		if(opt==0)
			c[++t2]=(Node1){x,y};
		else{
			if(st[x]>st[y]) swap(x,y);
			int lca=LCA(x,y);
			if(lca==x) node[++t1]=(Node){st[x],st[y],0,t2,t1};
			else node[++t1]=(Node){ed[x],st[y],lca,t2,t1};
		}
	}
	sort(node+1,node+1+t1);
	int l=1,r=0;
	for(ri i=1;i<=t1;++i){
		int ql=node[i].x,qr=node[i].y,qt=node[i].tim,lca=node[i].lca;
		while(l<ql) Add(dfn[l++]);
		while(l>ql) Add(dfn[--l]);
		while(r<qr) Add(dfn[++r]);
		while(r>qr) Add(dfn[r--]);
		while(now<qt) Change(l,r,++now);
		while(now>qt) Change(l,r,now--);
		if(lca) Add(lca);
		ans[node[i].id]=res;
		if(lca) Add(lca);
	}
	for(ri i=1;i<=t1;++i)
		print(ans[i]),puts("");
	return 0;
}